// 线性表的链式存储－单链表
// headless linklist

#include <stdio.h>
#include <malloc.h>

#define DataType int

typedef struct node
{
    DataType data;
    node *next;
} node, *LinkList;

LinkList Init(DataType initVal);
int Destory(LinkList &L);
int Length(LinkList L);
int Locate(LinkList L, DataType x);
int Insert(LinkList &L, DataType x);
int Insert(LinkList &L, int i, DataType x);
int Delete(LinkList &L, int i);
DataType GetItem(LinkList L, int i);
void printf(LinkList L);
int InverseForHeadless(LinkList &L); // 逆置单链表
int InverseForHeaded(LinkList &L);

// debug
int main()
{
    LinkList L = Init(0);
    for (int i = 0; i < 10; i++)
    {
        Insert(L, 2 * i + 1);
    }
    printf(" origin linklist: ");
    printf(L);

    printf("headless inverse: ");
    InverseForHeadless(L);
    printf(L);

    printf(" headed  inverse: ");
    InverseForHeaded(L);
    printf(L);

    printf("length of the list: %d\n", Length(L));

    printf("digit 7 position: %d\n", Locate(L, 7));

    printf("insert [21] in 2nd position: ");
    Insert(L, 1, 21);
    printf(L);

    Destory(L);
    printf(L);

    return 0;
}

int InverseForHeadless(LinkList &L)
{
    node *p = L->next;
    L->next = NULL; // 头插，第一个插入的是最后一个元素
    while (p != NULL)
    {
        node *next = p->next;
        p->next = L;
        L = p;
        p = next;
    }
    return 1;
}

int InverseForHeaded(LinkList &L)
{
    node *p = L->next;
    L->next = NULL;
    while (p != NULL)
    {
        node *next = p->next;
        p->next = L->next;
        L->next = p;
        p = next;
    }
    return 1;
}

void printf(LinkList L)
{
    node *p = L;
    printf("[");
    while (p != NULL)
    {
        if (p != L)
            printf(", ");
        printf("%d", p->data);
        p = p->next;
    }
    printf("]\n");
}

LinkList Init(DataType initVal)
{
    node *initNode = (node *)malloc(sizeof(node));
    initNode->data = initVal;
    initNode->next = NULL;
    LinkList L = initNode;
    return L;
}

int Destory(LinkList &L)
{
    if (L != NULL)
    {
        Destory(L->next);
        free(L);
    }
    return 1;
}

int Length(LinkList L)
{
    int len = 0;
    node *p = L;
    while (p != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

int Locate(LinkList L, DataType x)
{
    node *p = L;
    int i = 1;
    while (p != NULL)
    {
        if (p->data == x)
        {
            return i;
        }
        p = p->next;
        ++i;
    }
    return 0; // 没找到元素
}

// 插入无具体位置要求 采用头插 快速
int Insert(LinkList &L, DataType x)
{
    node *newNode = (node *)malloc(sizeof(node));
    newNode->data = x;
    newNode->next = L;
    L = newNode;
    return 1;
}

// 有位置要求的插入
int Insert(LinkList &L, int i, DataType x)
{
    // 在第i个位置之前插入
    // 即在第i-1个位置之后插入
    // 即在第i-2个索引位置之后插入
    node *p = L;
    for (int j = 0; j < i - 1 && p != NULL; j++)
    {
        p = p->next;
    }
    if (p != NULL)
    {
        node *newNode = (node *)malloc(sizeof(node));
        newNode->data = x;
        newNode->next = p->next;
        p->next = newNode;
    }
    return p != NULL;
}
